Modern electronic computing systems, such as microprocessor systems, typically include a processor and datapath configured to receive and process instructions. Certain systems allow for out of order instruction execution, wherein instructions can issue and be executed out of their order in the underlying program code. An out of order execution system must account for dependencies between instructions.
Generally, a dependency occurs where an instruction requires data from sources that are themselves the result of another instruction. For example, in the instruction sequence:
ADD $8, $7, $5
SW $9, (0)$8
The ADD (add) instruction adds the contents of register $7 to the contents of register $5 and puts the result in register $8. The SW (store word) instruction stores the contents of register $9 at the memory location address found in $8. As such, the SW instruction must wait for the ADD instruction to complete before storing the contents of register $8. The SW instruction therefore has a dependency on the ADD instruction. The illustrated dependency is also known as a read-after-write (RAW) dependency.
One common approach to tracking dependencies is a “dependency matrix,” such as that described in U.S. Pat. Nos. 6,065,105 and 6,334,182. Generally, a conventional dependency matrix includes rows and columns. Each bit or element, i.e., the intersection of one row and one column, corresponds to a dependency of an instruction in the issue queue. Each instruction in the issue queue is associated with a particular row in the dependency matrix, with the read-after-write (RAW) dependencies noted by bits set on a given column within that row.
As a given resource becomes available, the dependency matrix clears the column associated with that resource, setting all locations in the column to zero. Once a given instruction (row) has all of its RAW dependencies resolved, i.e. once all columns in that row have been set to zero, then the instruction is ready to issue.
As new instructions enter the issue queue, allocation logic assigns the new instructions to a position within the dependency matrix. The dependency matrix logic checks sources for that instruction against a destination register file. A match between an entering instruction's source and a pending instruction's destination indicates that the entering instruction is dependent on the pending entry, and the dependency matrix logic sets the bit in the appropriate position in the dependency matrix. The newly entered instruction will not issue from the issue queue until after the instruction on which it depends has issued, as indicated by the dependency matrix.
Conventional dependency matrices include a single write port and a single read port for each instruction queue. For example, FIG. 1 illustrates a prior art system 100. As shown in FIG. 1, a uni-queue (UQ) dependency matrix 110 couples to a read port 112, a write port 114, and a clear port 116. Dependency matrix 110 tracks dependencies in a uni-queue, and is made up of a number of cells arranged in a matrix (not shown). Write port 114 writes dependency information to the matrix 110 cells and read port 112 reads the stored dependency information from the matrix 110 cells. Clear port 116 clears vertical columns of matrix 110 cells, typically after an instruction executes (thereby satisfying the dependencies associated with the executing instruction).
Prior art system 100 includes another dependency matrix, load miss queue (LMQ) dependency matrix 120. As with matrix 110, matrix 120 couples to a read port 122, write port 124, and clear port 126. Read port 122, write port 124, and clear port 126 perform similar functions as read port 112, a write port 114, and a clear port 116. In a system with many various instruction queues, each with its own dependency matrix, the read, write, and clear ports can consume a relatively large amount of power and take up a relatively large amount of chip space.
Therefore, there is a need for a system and/or method for a dependency matrix that addresses at least some of the problems and disadvantages associated with conventional systems and methods.